Вперед: Метод простых итераций Наверх: Приближённое нахождение корней уравнений Назад: Метод простого перебора  

Метод половинного деления

Снова предположим, что корень отделён на отрезке $ [a;b]$ и знаки $ f(a)$ и $ f(b)$ различны (функция $ f(x)$ меняет знак при переходе через корень $ x^*$).

Положим $ a_0=a$ и $ b_0=b$ и вычислим значения функции в левом конце отрезка, $ f(a_0)$, и в его середине $ c_0=\dfrac{a_0+b_0}{2}$: $ f(c_0)$. Сравним знаки чисел $ f(a_0)$ и $ f(c_0)$. Если эти знаки различны, то корень $ x^*$ лежит в интервале $ (a_0;c_0)$; если же одинаковы, то тогда различны знаки $ f(c_0)$ и $ f(b_0)$, и корень лежит в интервале $ (c_0;b_0)$. (Возможен ещё случай $ f(c_0)=0$; тогда корень $ x^*=c_0$ уже найден.) В обоих случаях смены знака корень оказывается отделён на отрезке $ [a_0;c_0]$ либо $ [c_0;b_0]$, длина которого ровно в два раза меньше длины исходного отрезка $ [a_0;b_0]=[a;b]$. Обозначим этот отрезок половинной длины через $ [a_1;b_1]$ (то есть положим $ a_1=a_0;b_1=c_0$ в случае, когда $ f(a_0)$ и $ f(c_0)$ разных знаков, и $ a_1=c_0;b_1=b_0$ в случае, когда $ f(a_0)$ и $ f(c_0)$ одного знака).

Далее повторим процесс для отрезка $ [a_1;b_1]$: снова отыщем его середину $ c_1$, найдём значение функции $ f(c_1)$ и сравним знак этого числа со знаком $ f(a_1)$; если знаки разные, то корень отделён на $ [a_2;b_2]=[a_1;c_1]$, если одинаковые, то на $ [a_2;b_2]=[c_1;b_1]$ (или же оказывается, что $ f(c_1)=0$; тогда корень найден). Длина отрезка, на котором отделён корень, уменьшилась ещё в два раза.

Рис.9.2.Последовательное деление отрезка пополам и приближение к корню $ x^*$


Поступая тем же образом и далее, получаем, что после $ k$ делений длина отрезка, на котором лежит корень, сокращается в $ 2^k$ раз и становится равной $ {\delta}_k=\dfrac{b-a}{2^k}$ (если корень не был точно определён на каком-то предыдущем этапе, то есть не совпал с $ c_i$ при некотором $ i$). Пусть $ {\varepsilon}$ -- заданная точность, с которой требуется отыскать корень. Процесс деления отрезков следует остановить, как только станет верным неравенство $ 2{\delta}_k\leqslant {\varepsilon}$. Очевидно, что если при этом положить

$\displaystyle \wt x=c_k=\dfrac{a_k+b_k}{2},$

то расстояние от корня $ x^*$, лежащего где-то в интервале $ (a_k;b_k)$, до середины этого интервала $ \wt x$ будет не больше $ {\varepsilon}$, то есть приближённое равенство $ x^*\approx\wt x$ будет выполнено с нужной точностью.

        Пример 9.5   Снова рассмотрим уравнение $ x^3+2x^2+3x+5=0$. Пусть корень этого уравнения требуется вычислить с точностью $ {\varepsilon}=0.001$. Начинаем решение методом половинного деления с отрезка $ [-2;-1]$, на котором отделён корень $ x^*$.

Последовательно находим значение функции в серединах получающихся отрезков:

\begin{multline*} f(-1.5)=1.625;f(-1.75)=0.515625;f(-1.875)=-0.185547;\dots;\\ f(-1.841797)=0.011269, \end{multline*}

после чего вычисления прекращаются на девятом шаге, так как очередной отрезок имеет длину $ \dfrac{1}{2^9}=\dfrac{1}{512}<2{\varepsilon}=\dfrac{1}{500}.$ При этом середина последнего отрезка -- это точка $ -1.842773$. Получаем, что приближённое значение $ \wt x$ корня $ x^*$ с точностью до $ 0.001$ равно $ \wt x\approx-1.843$.     

Поскольку при каждом делении отрезка приходится ровно один раз вычислять значение функции $ f(x)$ (в том из концов нового отрезка, в котором это значение не было вычислено на предыдущих этапах), то в среднем придётся для нахождения корня с точностью $ {\varepsilon}$ вычислить значение функции $ N=k+1$ раз. Число $ k$ можно определить из неравенства $ \dfrac{b-a}{2^k}\leqslant 2{\varepsilon}$, откуда

$\displaystyle N=k+1=\left\lceil\log_2\dfrac{b-a}{2{\varepsilon}}\right\rceil+1.$

Это значение $ N$ при малых $ {\varepsilon}$ много меньше того значения $ N=\left\lceil\dfrac{b-a}{2{\varepsilon}}\right\rceil+1$, которое мы получили, анализируя метод простого перебора.

Заметим, что метод деления отрезка пополам, как и метод простого перебора, не предъявляет никаких требований к гладкости функции (то есть к существованию её производной): достаточно, чтобы функция была непрерывной.

Далее мы рассмотрим более быстрые методы, в которых наличие производной будет играть существенную роль.


Вперед: Метод простых итераций Наверх: Приближённое нахождение корней уравнений Назад: Метод простого перебора